#define _CRT_SECURE_NO_WARNINGS
#include"sort.h"

void heap_adjust(int (&arr)[10],int size, int parent)
{
	while (parent <= (size - 2) / 2)
	{
		int child = parent * 2 + 1;
		if (child + 1 <= size - 1)
		{
			if (arr[child] < arr[child + 1])
				child += 1;
		}
		if (arr[child] > arr[parent])
			swap(arr[child], arr[parent]);
		parent = child;
	}

}

//total time complexity: O(N * logN)
void heap_sort(int(&arr)[10])
{
	//create heap
	//time complexity: O(N)
	for (int i = 4; i >= 0; i--)
	{
		heap_adjust(arr, 10, i);
	}

	//sort start
	//time complexity: O(N * logN)
	int n = 9;
	while (n > 0)
	{
		swap(arr[0], arr[n]);
		heap_adjust(arr, n, 0);
		n--;
	}
	swap(arr[0], arr[1]);

}

void display_date_ordinary(int(&arr)[10])
{
	for (int i = 0; i < 10; i++)
		cout << arr[i] << " ";
	cout << endl;
}

void direct_select_sort(array<int, 10>&arr)
{
	int begin = 0;
	int end = 9;
	while (begin < end)
	{
		int maxi = end;
		int mini = begin;
		for (int i = begin; i < end; i++)
		{
			if (arr[mini] > arr[i])
				mini = i;
			if (arr[maxi] < arr[i])
				maxi = i;
		}
		swap(arr[begin], arr[mini]);
		if (maxi == begin)
			maxi = mini;
		swap(arr[end], arr[maxi]);
		begin++;
		end--;
	}
}